home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / cagd_lib / bzr2poly.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-12-31  |  15.9 KB  |  437 lines
  1. /******************************************************************************
  2. * Bzr2Poly.c - Bezier to polygon/polylines conversion routines.              *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Mar. 90.                          *
  5. ******************************************************************************/
  6.  
  7. #include "cagd_loc.h"
  8.  
  9. #define VEC_FIELD_TRIES    10
  10. #define VEC_FIELD_START_STEP 1e-6
  11.  
  12. /*****************************************************************************
  13. * DESCRIPTION:                                                               M
  14. *   Routine to convert a single Bezier surface to set of triangles         M
  15. * approximating it. FineNess is a fineness control on result and the larger  M
  16. t is more triangles may result. A value of 10 is a good start value.         M
  17. * NULL is returned in case of an error, otherwise list of CagdPolygonStruct. M
  18. *                                                                            *
  19. * PARAMETERS:                                                                M
  20. *   Srf:              To approximate into triangles.                         M
  21. *   FineNess:         Control on accuracy, the higher the finer.             M
  22. *   ComputeNormals:   If TRUE, normal information is also computed.          M
  23. *   FourPerFlat:      If TRUE, four triangles are created per flat surface.  M
  24. *                     If FALSE, only 2 triangles are created.                M
  25. *   ComputeUV:        If TRUE, UV values are stored and returned as well.    M
  26. *                                                                            *
  27. * RETURN VALUE:                                                              M
  28. *   CagdPolygonStruct *:  A list of polygons with optional normal and/or     M
  29. *                         UV parametric information.                         M
  30. *                         NULL is returned in case of an error.              M
  31. *                                                                            *
  32. * KEYWORDS:                                                                  M
  33. *   BzrSrf2Polygons, polygonization, surface approximation                   M
  34. *****************************************************************************/
  35. CagdPolygonStruct *BzrSrf2Polygons(CagdSrfStruct *Srf,
  36.                    int FineNess,
  37.                    CagdBType ComputeNormals,
  38.                    CagdBType FourPerFlat,
  39.                    CagdBType ComputeUV)
  40. {
  41.     int i, j, FineNessU1, FineNessV1, FineNessU, FineNessV, BaseIndex;
  42.     CagdRType *Pt;
  43.     CagdPointType
  44.     PType = Srf -> PType;
  45.     CagdPtStruct PtCenter, *Pt1, *Pt2, *Pt3, *Pt4, *PtMesh, *PtMeshPtr;
  46.     CagdUVStruct UVCenter, *UVMeshPtr,
  47.     *UV1 = NULL,
  48.     *UV2 = NULL,
  49.     *UV3 = NULL,
  50.     *UV4 = NULL,
  51.     *UVMesh = NULL;
  52.     CagdVecStruct NlCenter, *PtNrmlPtr,
  53.     *Nl1 = NULL,
  54.     *Nl2 = NULL,
  55.     *Nl3 = NULL,
  56.     *Nl4 = NULL,
  57.     *PtNrml = NULL;
  58.     CagdPolygonStruct *Poly,
  59.     *PolyHead = NULL;
  60.  
  61.     if (!CAGD_IS_BEZIER_SRF(Srf))
  62.     return NULL;
  63.  
  64.     /* Simple heuristic to estimate how many samples to compute. */
  65.     FineNessU = Srf -> UOrder * FineNess / 10;
  66.     FineNessV = Srf -> VOrder * FineNess / 10;
  67.  
  68.     if (FineNessU < 2)
  69.     FineNessU = 2;
  70.     if (FineNessV < 2)
  71.     FineNessV = 2;
  72.  
  73.     switch (_CagdLin2Poly) {
  74.     case CAGD_REG_POLY_PER_LIN:
  75.         break;
  76.         case CAGD_ONE_POLY_PER_LIN:
  77.         if (Srf -> UOrder == 2)
  78.         FineNessU = 2;
  79.         if (Srf -> VOrder == 2)
  80.         FineNessV = 2;
  81.         break;
  82.         case CAGD_ONE_POLY_PER_COLIN:
  83.         break;
  84.     }
  85.  
  86.     FineNessU1 = FineNessU - 1;
  87.     FineNessV1 = FineNessV - 1;
  88.  
  89.     /* Allocate a mesh to hold all vertices so common vertices need not be   */
  90.     /* Evaluated twice, and evaluate the surface at these mesh points.         */
  91.     PtMeshPtr = PtMesh = CagdPtArrayNew(FineNessU * FineNessV);
  92.  
  93.     for (i = 0; i < FineNessU; i++)
  94.     for (j = 0; j < FineNessV; j++) {
  95.         Pt = BzrSrfEvalAtParam(Srf, ((CagdRType) i) / FineNessU1,
  96.                         ((CagdRType) j) / FineNessV1);
  97.         CagdCoerceToE3(PtMeshPtr -> Pt, &Pt, -1, PType);
  98.         PtMeshPtr++;
  99.     }
  100.  
  101.     if (ComputeNormals) {
  102.     PtNrmlPtr = PtNrml = CagdVecArrayNew(FineNessU * FineNessV);
  103.     for (i = 0; i < FineNessU; i++)
  104.         for (j = 0; j < FineNessV; j++) {
  105.         Nl1 = BzrSrfNormal(Srf, ((CagdRType) i) / FineNessU1,
  106.                     ((CagdRType) j) / FineNessV1);
  107.  
  108.         if (PT_LENGTH(Nl1 -> Vec) < IRIT_EPSILON) {
  109.             int k = 0;
  110.             CagdRType U, V, UMin, UMax, VMin, VMax, UMid, VMid,
  111.                 Step = VEC_FIELD_START_STEP;
  112.  
  113.             CagdSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax);
  114.             UMid = (UMin + UMax) / 2;
  115.             VMid = (VMin + VMax) / 2;
  116.             U = ((CagdRType) i) / FineNessU1;
  117.             V = ((CagdRType) j) / FineNessV1;
  118.             while (PT_LENGTH(Nl1 -> Vec) < IRIT_EPSILON &&
  119.                k++ < VEC_FIELD_TRIES) {
  120.             U += U < UMid ? Step : -Step;
  121.             V += V < VMid ? Step : -Step;
  122.             Step *= 2.0;
  123.  
  124.             Nl1 = BzrSrfNormal(Srf, U, V);
  125.             }
  126.             if (k >= VEC_FIELD_TRIES)
  127.             CAGD_FATAL_ERROR(CAGD_ERR_CANNOT_COMP_VEC_FIELD);
  128.         }
  129.  
  130.         CAGD_COPY_VECTOR(*PtNrmlPtr, *Nl1);
  131.         PtNrmlPtr++;
  132.         }
  133.     }
  134.  
  135.     if (ComputeUV) {
  136.     UVMeshPtr = UVMesh = CagdUVArrayNew(FineNessU * FineNessV);
  137.     for (i = 0; i < FineNessU; i++)
  138.         for (j = 0; j < FineNessV; j++) {
  139.         UVMeshPtr -> UV[0] = ((CagdRType) i) / FineNessU1;
  140.         UVMeshPtr -> UV[1] = ((CagdRType) j) / FineNessU1;
  141.         UVMeshPtr++;
  142.         }
  143.     }
  144.  
  145.     /* Now that we have the mesh, create the polygons. */
  146.     for (i = 0; i < FineNessU1; i++)
  147.     for (j = 0; j < FineNessV1; j++) {
  148.         BaseIndex = i * FineNessV + j;
  149.         Pt1 = &PtMesh[BaseIndex];        /* Cache the four flat corners. */
  150.         Pt2 = &PtMesh[BaseIndex + 1];
  151.         Pt3 = &PtMesh[BaseIndex + FineNessV + 1];
  152.         Pt4 = &PtMesh[BaseIndex + FineNessV];
  153.  
  154.         if (ComputeNormals) {
  155.         Nl1 = &PtNrml[BaseIndex];
  156.         Nl2 = &PtNrml[BaseIndex + 1];
  157.         Nl3 = &PtNrml[BaseIndex + FineNessV + 1];
  158.         Nl4 = &PtNrml[BaseIndex + FineNessV];
  159.         }
  160.         if (ComputeUV) {
  161.         UV1 = &UVMesh[BaseIndex];
  162.         UV2 = &UVMesh[BaseIndex + 1];
  163.         UV3 = &UVMesh[BaseIndex + FineNessV + 1];
  164.         UV4 = &UVMesh[BaseIndex + FineNessV];
  165.         }
  166.  
  167.         if (FourPerFlat) {  /* Eval middle point and create 4 triangles. */
  168.         Pt = BzrSrfEvalAtParam(Srf, (i + 0.5) / FineNessU1,
  169.                             (j + 0.5) / FineNessV1);
  170.         CagdCoerceToE3(PtCenter.Pt, &Pt, -1, PType);
  171.  
  172.         if (ComputeNormals) {
  173.             /* Average the four normals to find the middle one. */
  174.             CAGD_COPY_VECTOR(NlCenter, *Nl1);
  175.             CAGD_ADD_VECTOR(NlCenter, *Nl2);
  176.             CAGD_ADD_VECTOR(NlCenter, *Nl3);
  177.             CAGD_ADD_VECTOR(NlCenter, *Nl4);
  178.             CAGD_NORMALIZE_VECTOR(NlCenter);
  179.         }
  180.  
  181.  
  182.         if (ComputeUV) {
  183.             UVCenter.UV[0] = (UV1 -> UV[0] + UV2 -> UV[0] +
  184.                       UV3 -> UV[0] + UV4 -> UV[0]) / 4.0;
  185.             UVCenter.UV[1] = (UV1 -> UV[1] + UV2 -> UV[1] +
  186.                       UV3 -> UV[1] + UV4 -> UV[1]) / 4.0;
  187.         }
  188.  
  189.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  190.                     Pt1, Pt2, &PtCenter,
  191.                     Nl1, Nl2, &NlCenter,
  192.                     UV1, UV2, &UVCenter);
  193.  
  194.         if (Poly)
  195.             LIST_PUSH(Poly, PolyHead);
  196.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  197.                     Pt2, Pt3, &PtCenter,
  198.                     Nl2, Nl3, &NlCenter,
  199.                     UV2, UV3, &UVCenter);
  200.         if (Poly)
  201.             LIST_PUSH(Poly, PolyHead);
  202.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  203.                     Pt3, Pt4, &PtCenter,
  204.                     Nl3, Nl4, &NlCenter,
  205.                     UV3, UV4, &UVCenter);
  206.         if (Poly)
  207.             LIST_PUSH(Poly, PolyHead);
  208.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  209.                     Pt4, Pt1, &PtCenter,
  210.                     Nl4, Nl1, &NlCenter,
  211.                     UV4, UV1, &UVCenter);
  212.         if (Poly)
  213.             LIST_PUSH(Poly, PolyHead);
  214.         }
  215.         else {               /* Only two along the diagonal... */
  216.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  217.                     Pt1, Pt2, Pt3,
  218.                     Nl1, Nl2, Nl3,
  219.                     UV1, UV2, UV3);
  220.         if (Poly)
  221.             LIST_PUSH(Poly, PolyHead);
  222.         Poly = _CagdMakePolygon(ComputeNormals, ComputeUV,
  223.                     Pt3, Pt4, Pt1,
  224.                     Nl3, Nl4, Nl1,
  225.                     UV3, UV4, UV1);
  226.         if (Poly)
  227.             LIST_PUSH(Poly, PolyHead);
  228.         }
  229.     }
  230.  
  231.     CagdPtArrayFree(PtMesh, FineNessU * FineNessV);
  232.     if (ComputeNormals)
  233.     CagdVecArrayFree(PtNrml, FineNessU * FineNessV);
  234.     if (ComputeUV)
  235.     CagdUVArrayFree(UVMesh, FineNessU * FineNessV);
  236.  
  237.     return PolyHead;
  238. }
  239.  
  240. /*****************************************************************************
  241. * DESCRIPTION:                                                               M
  242. *   Routine to convert a single Bezier surface to NumOfIsolines polylines    M
  243. * in each parametric direction with SamplesPerCurve in each isoparametric    M
  244. * curve.                                                                     M
  245. *   Polyline are always E3 of CagdPolylineStruct type.                 M
  246. *   Iso parametric curves are sampled equally spaced in parametric space.    M
  247. *   NULL is returned in case of an error, otherwise list of                  M
  248. * CagdPolylineStruct.                                  M
  249. *                                                                            *
  250. * PARAMETERS:                                                                M
  251. *   Srf:                 Srf to extract isoparametric curves from.           M
  252. *   NumOfIsocurves:      To extarct from Srf in each (U or V) direction.     M
  253. *   SamplesPerCurve:     Fineness control on piecewise linear curve          M
  254. *                        approximation.                                      M
  255. *                                                                            *
  256. * RETURN VALUE:                                                              M
  257. *   CagdPolylineStruct *: List of polygons representing a piecewise linear   M
  258. *                         approximation of the extracted isoparamteric       M
  259. *                         curves or NULL is case of an error.                M
  260. *                                                                            *
  261. * KEYWORDS:                                                                  M
  262. *   BzrSrf2Polylines, polylines, isoparametric curves                        M
  263. *****************************************************************************/
  264. CagdPolylineStruct *BzrSrf2Polylines(CagdSrfStruct *Srf,
  265.                      int NumOfIsocurves[2],
  266.                      int SamplesPerCurve)
  267. {
  268.     int i;
  269.     CagdRType t;
  270.     CagdCrvStruct *Crv;
  271.     CagdPolylineStruct *Poly,
  272.     *PolyList = NULL;
  273.  
  274.     if (!CAGD_IS_BEZIER_SRF(Srf))
  275.     return NULL;
  276.  
  277.     /* Make sure requested format is something reasonable. */
  278.     if (SamplesPerCurve < 2)
  279.     SamplesPerCurve = 2;
  280.     if (NumOfIsocurves[0] < 2)
  281.     NumOfIsocurves[0] = 2;
  282.     if (NumOfIsocurves[1] <= 0)
  283.     NumOfIsocurves[1] = NumOfIsocurves[0];
  284.     else if (NumOfIsocurves[1] < 2)
  285.     NumOfIsocurves[1] = 2;
  286.  
  287.     for (i = 0; i < NumOfIsocurves[0]; i++) {
  288.     t = ((CagdRType) i) / (NumOfIsocurves[0] - 1);
  289.     if (t > 1.0)
  290.         t = 1.0;                     /* In case of round off error. */
  291.  
  292.     Crv = BzrSrfCrvFromSrf(Srf, t, CAGD_CONST_U_DIR);
  293.     Poly = BzrCrv2Polyline(Crv, SamplesPerCurve);
  294.     Poly -> Pnext = PolyList;
  295.     PolyList = Poly;
  296.     CagdCrvFree(Crv);
  297.     }
  298.  
  299.     for (i = 0; i < NumOfIsocurves[1]; i++) {
  300.     t = ((CagdRType) i) / (NumOfIsocurves[1] - 1);
  301.     if (t > 1.0)
  302.         t = 1.0;                     /* In case of round off error. */
  303.  
  304.     Crv = BzrSrfCrvFromSrf(Srf, t, CAGD_CONST_V_DIR);
  305.     Poly = BzrCrv2Polyline(Crv, SamplesPerCurve);
  306.     Poly -> Pnext = PolyList;
  307.     PolyList = Poly;
  308.     CagdCrvFree(Crv);
  309.     }
  310.  
  311.     return PolyList;
  312. }
  313.  
  314. /*****************************************************************************
  315. * DESCRIPTION:                                                               M
  316. *   Routine to extract from a bezier surface NumOfIsoline isocurve list      M
  317. * in each param. direction.                             M
  318. *   Iso parametric curves are sampled equally spaced in parametric space.    M
  319. *   NULL is returned in case of an error, otherwise list of CagdCrvStruct.   M
  320. *                                                                            *
  321. * PARAMETERS:                                                                M
  322. *   Srf:             To extract isoparametric curves from.                   M
  323. *   NumOfIsocurves:  In reach (U or V) direction                             M
  324. *                                                                            *
  325. * RETURN VALUE:                                                              M
  326. *   CagdCrvStruct *:  List of extracted isoparametric curves. These curves   M
  327. *                     inherit the order and continuity of the original Srf.  M
  328. *                     NULL is returned in case of an error.                  M
  329. *                                                                            *
  330. * KEYWORDS:                                                                  M
  331. *   BzrSrf2Curves, curves, isoparametric curves                              M
  332. *****************************************************************************/
  333. CagdCrvStruct *BzrSrf2Curves(CagdSrfStruct *Srf, int NumOfIsocurves[2])
  334. {
  335.     int i;
  336.     CagdRType t;
  337.     CagdCrvStruct *Crv,
  338.     *CrvList = NULL;
  339.  
  340.     if (!CAGD_IS_BEZIER_SRF(Srf))
  341.     return NULL;
  342.  
  343.     /* Make sure requested format is something reasonable. */
  344.     if (NumOfIsocurves[0] < 2)
  345.     NumOfIsocurves[0] = 2;
  346.     if (NumOfIsocurves[1] <= 0)
  347.     NumOfIsocurves[1] = NumOfIsocurves[0];
  348.     else if (NumOfIsocurves[1] < 2)
  349.     NumOfIsocurves[1] = 2;
  350.  
  351.     for (i = 0; i < NumOfIsocurves[0]; i++) {
  352.     t = ((CagdRType) i) / (NumOfIsocurves[0] - 1);
  353.     if (t > 1.0)
  354.         t = 1.0;                     /* In case of round off error. */
  355.  
  356.     Crv = CagdCrvFromSrf(Srf, t, CAGD_CONST_U_DIR);
  357.     Crv -> Pnext = CrvList;
  358.     CrvList = Crv;
  359.     }
  360.  
  361.     for (i = 0; i < NumOfIsocurves[1]; i++) {
  362.     t = ((CagdRType) i) / (NumOfIsocurves[1] - 1);
  363.     if (t > 1.0)
  364.         t = 1.0;                     /* In case of round off error. */
  365.  
  366.     Crv = CagdCrvFromSrf(Srf, t, CAGD_CONST_V_DIR);
  367.     Crv -> Pnext = CrvList;
  368.     CrvList = Crv;
  369.     }
  370.  
  371.     return CrvList;
  372. }
  373.  
  374. /*****************************************************************************
  375. * DESCRIPTION:                                                               M
  376. *   Routine to approx. a single Bezier curve as a polyline with             M
  377. * SamplesPerCurve samples. Polyline is always E3 CagdPolylineStruct type.    M
  378. *   Curve is sampled equally spaced in parametric space.                     M
  379. *   NULL is returned in case of an error, otherwise CagdPolylineStruct.         M
  380. *                                                                            *
  381. * PARAMETERS:                                                                M
  382. *   Crv:              To approximate as a polyline.                          M
  383. *   SamplesPerCurve:  Number of samples to approximate with.                 M
  384. *                                                                            *
  385. * RETURN VALUE:                                                              M
  386. *   CagdPolylineStruct *:  A polyline representing the piecewise linear      M
  387. *                          approximation from, or NULL in case of an error.  M
  388. *                                                                            *
  389. * KEYWORDS:                                                                  M
  390. *   BzrCrv2Polyline, piecewise linear approximation, polyline                M
  391. *****************************************************************************/
  392. CagdPolylineStruct *BzrCrv2Polyline(CagdCrvStruct *Crv, int SamplesPerCurve)
  393. {
  394.     int i, j,
  395.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv),
  396.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  397.     CagdRType *Polyline[CAGD_MAX_PT_SIZE], Scaler;
  398.     CagdPolylnStruct *NewPolyline;
  399.     CagdPolylineStruct *P;
  400.  
  401.     if (!CAGD_IS_BEZIER_CRV(Crv))
  402.     return NULL;
  403.  
  404.     /* Make sure requested format is something reasonable. */
  405.     if (SamplesPerCurve < 2 || Crv -> Order == 2)
  406.     SamplesPerCurve = 2;
  407.  
  408.     P = CagdPolylineNew(SamplesPerCurve);
  409.     NewPolyline = P -> Polyline;
  410.  
  411.     /* Allocate temporary memory to hold evaluated curve. */
  412.     for (i = 0; i < CAGD_MAX_PT_SIZE; i++)
  413.     Polyline[i] =
  414.         (CagdRType *) IritMalloc(sizeof(CagdRType) * SamplesPerCurve);
  415.  
  416.     if (MaxCoord > 3)
  417.     MaxCoord = 3;
  418.  
  419.     BzrCrvEvalToPolyline(Crv, SamplesPerCurve, Polyline);
  420.  
  421.     for (i = SamplesPerCurve - 1; i >= 0; i--) {  /* Convert to E3 polyline. */
  422.     if (IsNotRational)
  423.         Scaler = 1.0;
  424.     else
  425.         Scaler = Polyline[0][i];
  426.  
  427.     for (j = 0; j < MaxCoord; j++)
  428.         NewPolyline[i].Pt[j] = Polyline[j+1][i] / Scaler;
  429.     for (j = MaxCoord; j < 3; j++)
  430.         NewPolyline[i].Pt[j] = 0.0;
  431.     }
  432.     for (i = 0; i < CAGD_MAX_PT_SIZE; i++)
  433.     IritFree((VoidPtr) Polyline[i]);
  434.  
  435.     return P;
  436. }
  437.